Syntax and semantics

1 Syntax

The grammar for our language now looks like this:

\[ \definecolor{myblue}{RGB}{37, 104, 145} \newcommand{gt}[1]{{\color{myblue}\underline{#1}}\quad} \newcommand{gnt}[1]{\mathit{#1}\quad} \newcommand{\Program}{\gnt{Program}} \newcommand{\STR}{\gt{STR}} \newcommand{\Args}{\gnt{Args}} \newcommand{\Expr}{\gnt{Expr}} \newcommand{\Declarations}{\gnt{Declarations}} \newcommand{\Parameters}{\gnt{Parameters}} \newcommand{\Statements}{\gnt{Statements}} \newcommand{\Declaration}{\gnt{Declaration}} \newcommand{\Statement}{\gnt{Statement}} \newcommand{\DEF}{\gt{DEF}} \newcommand{\INT}{\gt{INT}} \newcommand{\VAR}{\gt{VAR}} \newcommand{\ASSIGN}{\gt{:=}} \newcommand{\SEMI}{\gt{;}} \newcommand{\INPUT}{\gt{input}} \newcommand{\IF}{\gt{if}} \newcommand{\ELSE}{\gt{else}} \newcommand{\WHILE}{\gt{while}} \newcommand{\RETURN}{\gt{return}} \newcommand{\prod}{\rightarrow\quad} \newcommand{\alt}{\ |\ \quad} \]

\[ \begin{align} \Program \prod & \Declarations \Statements\\ \\ \Declarations \prod & \Declaration \Declarations \\ \alt & \epsilon\\ \\ \Declaration \prod & \DEF \VAR \gt{(} \Parameters \gt{)} \gt{\{} \Statements \gt{\}}\\ \\ \Parameters \prod & \VAR \gt{,} \Parameters \\ \alt & \VAR\\ \alt & \epsilon\\ \\ \Statements \prod & \Statement \Statements \\ \alt & \epsilon\\ \\ \Statement \prod & \INPUT \VAR \SEMI \\ \alt & \gt{printString} \STR \SEMI \\ \alt & \gt{printNumber} \Expr \SEMI \\ \alt & \VAR \ASSIGN \Expr \SEMI \\ \alt & \IF \gt{(} \Expr \gt{)} \gt{\{} \Statements \gt{\}} \ELSE \gt{\{} \Statements \gt{\}}\\ \alt & \IF \gt{(} \Expr \gt{)} \gt{\{} \Statements \gt{\}}\\ \alt & \WHILE \gt{(} \Expr \gt{)} \gt{\{} \Statements \gt{\}}\\ \alt & \RETURN \Expr \SEMI \\ \alt & \RETURN \SEMI \\ \\ \Args \prod & \Expr \gt{,} \Args \\ \alt & \Expr\\ \alt & \epsilon\\ \\ \Expr \prod & \Expr \gt{+} \Expr \\ \alt & \Expr \gt{-} \Expr \\ \alt & \Expr \gt{*} \Expr \\ \alt & \gt{(} \Expr \gt{)} \\ \alt & \VAR \gt{(} \Args \gt{)}\\ \alt & \INT\\ \alt & \VAR \end{align} \]

Example program

Here is an example program in our language:

def factorial(n) {
  if (n) {
    return 1;
  }
    
  return (n * factorial(n - 1));
}

input n;
print factorial(n);

2 Semantics

Our language does not have explicit declarations for local variables. Therefore, an assignment statement in a function body can be ambiguous: Is the assignment creating a new local variable; or is the assignment updating the value of a parameter?

If the variable being assigned to is a parameter of the function, then our semantics will treat the assignment as updating the parameter value. Otherwise, the assignment will be treated as creating a new local variable.